package dataStructure.binaryTree;

/**
 * 平衡二叉树
 * 定义:首先它是一种特殊的二叉排序树，其次它的左子树和右子树都是平衡二叉树，
 * 且左子树和右子树的深度之差不超过1
 * 平衡因子:可以定义为左子树的深度减去右子树的深度
 * <p>
 * 平衡二叉树是对二叉排序树的优化，防止二叉排序树在最坏情况下平均查找时间为n，
 * 二叉排序树在此时形如一个单链表
 * 平衡二叉树查找元素的次数不超过树的深度，时间复杂度为logN
 */
public class AVLTree<E> {
    private TreeNode<E> root = null;
    /**
     * 树中元素个数
     */
    private int size = 0;

    public int size() {
        return size;
    }

    /**
     * @param p 最小旋转子树的根节点
     *          向左旋转之后p移到p的左子树处，p的右子树B变为此最小子树根节点，
     *          B的左子树变为p的右子树
     *          比如：     A(-2)                   B(1)
     *          \        左旋转       /   \
     *          B(0)     ---->       A(0)   \
     *          /   \                   \    \
     *          BL(0)  BR(0)              BL(0) BR(0)
     *          旋转之后树的深度之差不超过1
     */
    private void rotateLeft(TreeNode<E> p) {
        System.out.println("绕" + p.element + "左旋");
        if (p != null) {
            TreeNode<E> r = p.right;
            p.right = r.left;   //把p右子树的左节点嫁接到p的右节点，如上图，把BL作为A的右子节点
            if (r.left != null) //如果B的左节点BL不为空，把BL的父节点设为A
                r.left.parent = p;
            r.parent = p.parent;  //A的父节点设为B的父节点
            if (p.parent == null)         //如果p是根节点
                root = r;                 //r变为父节点，即B为父节点
            else if (p.parent.left == p)  //如果p是左子节点
                p.parent.left = r;        //p的父节点的左子树为r
            else                          //如果p是右子节点
                p.parent.right = r;       //p的父节点的右子树为r
            r.left = p;                   //p变为r的左子树，即A为B的左子树
            p.parent = r;                 //同时更改p的父节点为r，即A的父节点为B
        }
    }

//    A(9)         A(9)
//   /      L     /      R     C(5)
//  B(3)   -->   C(5)   -->   /   \
//   \          /            B(3)  A(9)
//    C(5)     B(3)
//   LR

//  A(5)       A(5)
//   \      R   \        L    C(6)
//    B(9) -->   C(6)   -->   /   \
//   /            \          A(5)  B(9)
//  C(6)           B(9)
//   RL
}
